Hachage : Stratégies de redimensionnement

La nécessité du réhachage

Pour garantir des performances souhaitées en $O(1)$ cas moyen pour la recherche et l'insertion, le Facteur de charge ( $\lambda = N/M$ ) doit être strictement limité, où $N$ est le nombre d'éléments et $M$ est la capacité du tableau.

Si $\lambda$ est autorisé à croître indéfiniment, les collisions augmentent exponentiellement, et la complexité moyenne du temps dégrade vers $O(N)$ .

Condition	Action déclenchée	Impact
$\lambda < \lambda_{max}$	Standard $O(1)$ insertion	Efficiency optimale maintenue.
$\lambda \geq \lambda_{max}$	Redimensionnement (réhachage)	Restaure $O(1)$ performance, mais entraîne un coût temporaire de $O(N)$ coût.

Seuils courants ( $\lambda_{max}$ ): 0,70 à 0,75.

Le processus de redimensionnement

Le redimensionnement exige le recalcul de l'indice de hachage pour chaque élément actuellement dans le tableau, un processus connu sous le nom de réhachage.

Détermination de la nouvelle capacité : Sélectionnez une nouvelle capacité $M_{new}$ , généralement double la capacité actuelle ( $M_{new} = 2M$ ). Cela garantit que le nouveau $\lambda$ est la moitié du seuil critique.
Création du tableau : Allouer un nouveau tableau de hachage de taille $M_{new}$ .
Itération sur les éléments : Parcourir tous les $N$ éléments existants dans l'ancien tableau.
Réhachage : Pour chaque clé $k$ , calculez l'index nouveau en utilisant le module mis à jour : $\text{index}' = h(k) \pmod{M_{new}}$
Insertion : Insérer l'élément dans le nouveau tableau à l'index $\text{index}'$ .

Remarque : Puisque le module change, copier simplement le tableau est impossible ; chaque élément doit être réinséré.

Coût amorti

Pourquoi le redimensionnement est-il $O(N)$

Le redimensionnement exige le traitement de tous les $N$ éléments, ce qui signifie que l'opération elle-même prend $O(N)$ temps, ce qui viole temporairement l'objectif de $O(1)$ insertion.

Analyse amortie

Nous utilisons Analyse amortie pour justifier ce coût. Si le tableau double sa taille à chaque redimensionnement (croissance exponentielle), le coût élevé de $O(N)$ est réparti sur un grand nombre d'insertions intermédiaires de $O(1)$ insertions.

Le coût moyen de toute insertion unique, en tenant compte du redimensionnement périodique de $O(N)$ , reste $O(1)$ .

📝 Quiz interactif

1. Un tableau de hachage a une capacité $M=50$ et un facteur de charge maximal $\lambda_{max} = 0,6$ . À quelle quantité d'éléments ( $N$ ) un redimensionnement doit-il être déclenché ?

A) $N = 25$
B) $N = 30$
C) $N = 31$
D) $N = 50$

2. Lors d'un redimensionnement, pourquoi ne pouvons-nous pas simplement copier les éléments de l'ancien tableau vers le nouveau, plus grand tableau ?

A) C'est plus lent au niveau computationnel que le réhachage.
B) L'indice de hachage dépend de la capacité du tableau ( $M$ ), qui a changé.
C) Cela causerait une fragmentation mémoire.
D) Les anciennes données sont dans un état en lecture seule.

3. Quelle est la complexité temporelle amortie d'une insertion dans un tableau de hachage qui double sa taille lors du redimensionnement ?

A) $O(N)$
B) $O(1)$
C) $O(\log N)$
D) $O(N \log N)$

4. Quelle est la conséquence principale de ne pas redimensionner un tableau de hachage lorsque son facteur de charge devient trop élevé ?

A) La performance dégrade vers $O(N)$ en raison d'une augmentation des collisions.
B) Le tableau va manquer de mémoire immédiatement.
C) La fonction de hachage elle-même devient invalide.
D) Le tableau supprime automatiquement les éléments les plus anciens.